package sort.leetcode_215_medium;

public class HeapSolution {
    public int findKthLargest(int[] nums, int k){
        //构建长度为k的最小堆
        buildHeap(nums, k);
        //调整堆，来寻找第K个最大元素
        for (int i = k; i < nums.length; i++){
            if(nums[i] > nums[0]){
                //如果 当前元素 > 堆顶元素 交换
                swap(nums, i, 0);
                //重新调整成 最小堆
                downAdjust(nums, 0, k);
            }
        }
        return nums[0];
    }

    /**
     * 构建最小堆
     */
    public void buildHeap(int[] nums, int k){
        for(int i = k / 2 - 1; i >=0; i--){
            downAdjust(nums, i, k);
        }
    }

    /**
     * 二叉堆的下沉操作
     */
    public void downAdjust(int[] nums, int pIndex, int heapSize){
        int cIndex = pIndex * 2 + 1;
        while(cIndex < heapSize){
            if(cIndex + 1 < heapSize && nums[cIndex + 1] < nums[cIndex]){
                cIndex++;
            }
            if(nums[pIndex] < nums[cIndex]){
                break;
            }
            swap(nums, pIndex, cIndex);
            pIndex = cIndex;
            cIndex = pIndex * 2 + 1;
        }
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
